
/**
 * AVL Node in the {@link AVLTree}.
 */
public class AVLNode {
	/** The size of the tree. */
	private int size;

	/** The height of the tree. */
	private int height;

	/** The key of the current node. */
	private Object key;

	/** The data of the current node. */
	private Object data;

	/** The {@link Comparator} used by the node. */
	private Comparator comp;

	/** All the nodes pointed by the current node. */
	private AVLNode left,right,parent,succ,pred;

	/** The node to start balance from. */
	private AVLNode toBalance;

	/**
	 * Instantiates a new AVL node.
	 *
	 * @param key the key of the node
	 * @param data the data that the node should keep
	 * @param comp the comparator to be used in the tree
	 */
	public AVLNode(Object key, Object data, Comparator comp) {
		this(key,data,comp,null);
	}

	/**
	 * Instantiates a new AVL node.
	 *
	 * @param key the key of the node
	 * @param data the data that the node should keep
	 * @param comp the comparator to be used in the tree
	 * @param parent the parent of the created node
	 */
	public AVLNode(Object key, Object data, Comparator comp, AVLNode parent) {
		this.data = data;
		this.key = key;
		this.comp = comp;
		this.parent = parent;

		this.left = null;
		this.right = null;
		this.succ = null;
		this.pred = null;

		this.size = 1;
		this.height = 0;

		this.toBalance=null;//do we need to balance one its children
	}

	/**
	 * Adds the given data to the tree.
	 *
	 * @param key the key
	 * @param data the data
	 * @return the root of the tree after insertion and rotations
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 */
	public AVLNode add(Object key,Object data) {
		int compRes = comp.compare(this.key, key);
		this.size++;
		if (compRes>0){ // enter to LEFT CHILD
			if (this.left==null){
				this.left = new AVLNode(key, data, comp, this);
				updateLeftSuccPredAdd();
				if (this.right==null)
					this.height=1;
			}
			else {
				this.left.add(key, data);
			}
		}
		else { // enter to RIGHT CHILD
			if (this.right==null){
				this.right = new AVLNode(key, data, comp, this);
				updateRightSuccPredAdd();
				if (this.left==null) //thats a new level
					this.height=1;
			}
			else {
				this.right.add(key, data);
			}
		}
		updateHeight();
		updateParent();
		balance();
		return this;
	}

	/**
	 * Removes a Node which key is equal (by {@link Comparator}) to the given argument.
	 * Recursive method for {remove} method 
	 * 
	 * @param key the key
	 * @return the root after deletion and rotations
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 */
	private AVLNode removeRecursive(Object key) {
		int compRes = comp.compare(key, this.key);
		AVLNode y=null,x=null,z=this,toBalance=null;
		AVLNode yPred=null,ySucc=null;
		if (compRes==0){
			//choosing y to copy and then remove
			if (this.left==null | this.right==null){
				y=z;
			}
			else if (this.pred!=null){
				y=z.pred;
			}
			else if (this.succ!=null){
				y=z.succ;
			}
			//saving y's pred and succ
			yPred=y.pred;
			ySucc=y.succ;

			//getting one of y's children, or nullify x
			if (y.left!=null)
				x=y.left;
			else
				x=y.right;
			//updating x's parent
			if (x!=null){
				x.parent=y.parent;
			}
			//update pred and succ
			if (yPred!=null){
				yPred.succ=ySucc;
			}
			if (ySucc!=null){
				ySucc.pred=yPred;
			}
			//get the current root
			AVLNode goToRoot=this;
			while (goToRoot.parent!=null)
				goToRoot=goToRoot.parent;
			//remove y
			if (y.parent==null){//x is the new root
				return x;
			}
			else{//making y's parent to point to x ~> (jump over x)
				if (y==y.parent.left){
					y.parent.left=x;
				}
				else{
					y.parent.right=x;	
				}
				// need to use toBalance as it's recursive up and we must get to the root
				toBalance=y.parent;

				goToRoot.toBalance=toBalance.parent;
				toBalance.updateSizeRec();//all nodes size upwards are smaller
				toBalance.updateHeightRec();//maybe all nodes height upwards are smaller
			}
			//copy y's data into z
			if (y!=z){
				z.key=y.key;
				z.data=y.data;
			}
			//delete y
			y=null;
		}
		else {
			if (compRes>0) {
				if (this.right!=null)
					this.right.removeRecursive(key);
			}
			else {
				if (this.left!=null)
					this.left.removeRecursive(key);
			}
		}
		return this;
	}

	/**
	 * Removes a Node which key is equal (by {@link Comparator}) to the given argument.
	 *
	 * @param key the key
	 * @return the root after deletion and rotations
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 */
	public AVLNode remove(Object key) {
		
		AVLNode ans=this.removeRecursive(key);

		if (toBalance!=null)
			toBalance.balanceRemoveRec();//recursive up balance
		return ans;
	}

	/**
	 * Update pred & succ fields after adding to left child O(1)
	 * 
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 */
	private void updateLeftSuccPredAdd() {
		this.left.succ=this;
		this.left.pred=this.pred;
		if (this.pred!=null)
			this.pred.succ=this.left;
		this.pred=this.left;
	}
	
	/**
	 * Update pred & succ fields after adding to right child O(1)
	 * 
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 */
	private void updateRightSuccPredAdd() {
		this.right.pred=this;
		this.right.succ=this.succ;
		if (this.succ!=null)
			this.succ.pred=this.right;
		this.succ=this.right;
	}
	/**
	 * Checks if the node is balanced, and changes it accordingly.
	 * 
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 */
	private void balance() {
		//gets the heights of the node's children
		int leftH=0,rightH;
		if (this.left!=null)
			leftH=this.left.height;
		else 
			leftH=-1;
		if (this.right!=null)
			rightH=this.right.height;
		else
			rightH=-1;
		//checks if the node is balanced
		if (Math.abs(leftH-rightH)>1){
			int subR,subL;
			if (leftH-1>rightH){//checks who's bigger
				if (this.left.right!=null)
					subR=this.left.right.height;
				else
					subR=-1;
				if (this.left.left!=null)
					subL=this.left.left.height;
				else
					subL=-1;
				if (subR>subL){
					//case 3
					this.left.rotateLeft();//makes it case 1
					this.left.updateParent();
					this.left.updateHeight();
					this.rotateRight();
				}
				else this.rotateRight(); //case 1
			}
			else if (rightH-1>leftH){
				if (this.right.right!=null)
					subR=this.right.right.height;
				else
					subR=-1;
				if (this.right.left!=null)
					subL=this.right.left.height;
				else
					subL=-1;
				if (subL>subR){
					//case 4
					this.right.rotateRight();//makes it case 2
					this.right.updateParent();
					this.right.updateHeight();
					this.rotateLeft();

				}
				else this.rotateLeft();  //case 2

			}
			updateParent();
			updateHeight();
		}
	}
	/**
	 * Checks if the node is balanced, and changes it accordingly.
	 * Recursive method - goes all the way up to the root.
	 * 
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 */
	private void balanceRemoveRec() {

		this.balance();

		if (this.parent!=null)
			this.parent.balanceRemoveRec();
	}


	private void rotateRight() {
		AVLNode leftLeftChild=null;
		AVLNode leftRightChild=null;
		AVLNode rightChild=null;
		//the new right child is THIS
		AVLNode oldThis = new AVLNode(this.key, this.data, comp);
		oldThis.succ=this.succ;
		if (this.succ!=null) this.succ.pred=oldThis;
		oldThis.pred=this.pred;
		if (this.pred!=null) this.pred.succ=oldThis;
		//saves the nodes
		if (this.left!=null) {
			leftLeftChild=this.left.left;
			leftRightChild=this.left.right;
		}
		if (this.right!=null){
			rightChild=this.right;
		}
		//update all fields...
		this.key=this.left.key;
		this.data=this.left.data;

		this.pred=this.left.pred;
		if (this.pred!=null) this.pred.succ=this;
		this.succ=this.left.succ;
		if (this.succ!=null) this.succ.pred=this;
		//creates the new THIS. actual rotation(~magic) happens here. 
		this.left=leftLeftChild;
		this.right = oldThis;
		this.right.right=rightChild;
		if (this.right!=null && this.right.right!=null) this.right.right.parent=this.right;
		this.right.left=leftRightChild;
		if (this.right!=null && this.right.left!=null) this.right.left.parent=this.right;
		//update last few fields
		this.right.updateHeight();
		this.right.updateSize();
		this.right.parent=this;

	}

	private void rotateLeft() {
		//Symmetrically identical to rotateRight
		AVLNode rightLeftChild=null;
		AVLNode rightRightChild=null;
		AVLNode leftChild=null;
		AVLNode oldThis = new AVLNode(this.key, this.data, comp);
		oldThis.succ=this.succ;
		if (this.succ!=null) this.succ.pred=oldThis;
		oldThis.pred=this.pred;
		if (this.pred!=null) this.pred.succ=oldThis;

		oldThis.succ=this.succ;
		oldThis.pred=this.pred;
		if (this.right!=null) {
			rightLeftChild=this.right.left;
			rightRightChild=this.right.right;
		}
		if (this.left!=null){
			leftChild=this.left;
		}

		this.key=this.right.key;
		this.data=this.right.data;

		this.pred=this.right.pred;
		if (this.pred!=null) this.pred.succ=this;
		this.succ=this.right.succ;
		if (this.succ!=null) this.succ.pred=this;

		this.right=rightRightChild;
		this.left = oldThis;
		this.left.left=leftChild;
		if (this.left!=null && this.left.left!=null) this.left.left.parent=this.left;
		this.left.right=rightLeftChild;
		if (this.left!=null && this.left.right!=null) this.left.right.parent=this.right;

		this.left.parent=this;
		this.left.updateHeight();
		this.left.updateSize();

	}


	/**
	 * Gets all the elements between the K'th and the H'th element in the tree.
	 *
	 * @param k A number between 1 and @link {@link #size()}
	 * @param h A number between k and @link {@link #size()}
	 * @return elements between k and h
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 */
	public LinkedList getKthTillHth(int k, int h) {
        LinkedList ans=new LinkedList();
        AVLNode tmp=findKthNode(k);
        h=h-k+1;
        while (tmp!=null && h>0){
            ans.addLast(tmp.data);
            tmp=tmp.succ;
            h--;
        }
        return ans;
    }


	/**
	 * Finds a Node which key is equal (by {@link Comparator}) to the given argument.
	 *
	 * @param key the key of the node
	 * @return the data of the found Node, returns null if node isn't found
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 */
	public Object find(Object key) {
		AVLNode ans=findNode(key);
		if (ans!=null)
			return ans.data;
		else
			return null;
	}
	
	/**
	 * Finds a Node which key is equal (by {@link Comparator}) to the given argument.
	 *
	 * @param key the key of the node
	 * @return the found Node, returns null if node isn't found
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 */
	private AVLNode findNode(Object key) {
		int compRes = comp.compare(this.key, key);
		if (compRes>0){ // search LEFT
			if (this.left!=null){
				return this.left.findNode(key);
			}
		}
		else if (compRes<0){//search RIGHT
			if (this.right!=null){
				return this.right.findNode(key);
			}
		}
		else if (compRes==0){//found IT
			return this;
		}
		return null;
	}

	/**
	 * Find K'th element in the tree.
	 *
	 * @param k is a number between 1 and {@link #size()}
	 * @return the object
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 */
	public Object findKthElement(int k){
		AVLNode ans=findKthNode(k);
		if (ans!=null)
			return ans.data;
		else
			return null;
	}
	/**
	 * Find K'th element in the tree.
	 *
	 * @param k is a number between 1 and {@link #size()}
	 * @return the node
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 */
	private AVLNode findKthNode(int k){
		int sizeLeft;
		if (this.left!=null)
			sizeLeft=this.left.size;
		else
			sizeLeft=0;

		if (sizeLeft+1==k)
			return this;//THIS is the k's element
		else if (this.left!=null && k<=sizeLeft)
			return this.left.findKthNode(k);//search left side
		else if (this.right!=null && k>sizeLeft+1)
			return this.right.findKthNode(k-(sizeLeft+1));//search right side
		else//didn't find
			return null;
	}
	/**
	 * Update height based on children O(1)
	 *
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 */
	private void updateHeight(){
		int leftH,rightH;
		if (this.left!=null)
			leftH=this.left.height;
		else 
			leftH=0;
		if (this.right!=null)
			rightH=this.right.height;
		else
			rightH=0;
		if (this.left==null && this.right==null)
			this.height=0;
		else
			this.height=Math.max(leftH,rightH)+1;
	}
	
	/**
	 * Update height based on children O(1).
	 * RECURSIVE (up) method
	 *
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 */
	private void updateHeightRec(){
		//recursive up "updateHeight()"
		this.updateHeight();
		if (this.parent!=null)
			this.parent.updateHeightRec();
	}
	
	/**
	 * Updates both children and let them know who's their daddy.
	 *
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 */
	private void updateParent(){
		if (this.left!=null){
			this.left.parent=this;
			if (this.left.left!=null){
				this.left.left.parent=this.left;
			}

			if (this.left.right!=null){
				this.left.right.parent=this.left;
			}
		}

		if (this.right!=null){
			this.right.parent=this;
			if (this.right.left!=null){
				this.right.left.parent=this.right;
			}

			if (this.right.right!=null){
				this.right.right.parent=this.right;
			}
		}
	}
	/**
	 * Updates size based on the children.
	 *
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 */
	private void updateSize(){
		int leftS,rightS;
		if (this.left!=null){
			leftS=this.left.size;
		}
		else 
			leftS=0;
		if (this.right!=null){
			rightS=this.right.size;
		}
		else
			rightS=0;
		this.size=leftS+rightS+1;
		if (this.parent!=null)
			this.parent.updateSize();
	}
	/**
	 * Updates size based on the children.
	 * RECURSIVE (up) method.
	 *
	 * @author <b>Matan Mizrahi,Ofir Naor</b>
	 */
	private void updateSizeRec(){
		//recursive up "updateSize()"
		this.updateSize();
		if (this.parent!=null)
			this.parent.updateSizeRec();

	}


	/**
	 * Return the size of the tree.
	 *
	 * @return the size of the tree.
	 */
	public int size(){
		return this.size;
	}


	/**
	 * Return the height of the tree.
	 *
	 * @return the height of the tree.
	 */
	public int height(){
		return this.height;
	}

	/**
	 * Gets the key of the current node.
	 *
	 * @return the key
	 */
	public Object getKey() {
		return this.key;
	}

	/* (non-Javadoc)
	 * @see java.lang.Object#toString()
	 */
	@Override
	public String toString() {
		return "(" + this.key + " " + this.data + ")";
	}

	/**
	 * Load the current tree (starting with the current node) into a {@link StringBuilder} in a in-order way.
	 *
	 * @param sb the {@link StringBuilder}
	 */
	public void inOrderToString(StringBuilder sb){
		if (this.left != null){	
			this.left.inOrderToString(sb);
			sb.append(this.key + " -> " + left.key + ";\n");
		}else
		{
			sb.append("nulll"+this.key+" [shape=point];\n");
			sb.append(this.key + " -> nulll" + this.key + ";\n");
		}

		sb.append(this.key + "[label=\""+this.data+",s:"+this.size()+",h:"+this.height()+"\"];\n");
		if (this.parent != null)
			sb.append(this.key + " -> " + parent.key + "[style=dashed];\n");

		if (this.right != null){
			this.right.inOrderToString(sb);
			sb.append(this.key + " -> " + right.key + ";\n");
		}else
		{
			sb.append("nullr"+this.key+" [shape=point];\n");
			sb.append(this.key + " -> nullr" + this.key + ";\n");
		}
	}

	/**
	 * Gets the predecessor of the current node.
	 *
	 * @return the predecessor
	 */
	public AVLNode getPred() {
		return pred;
	}

	/**
	 * Gets the successor of the current node.
	 *
	 * @return the successor
	 */
	public AVLNode getSucc(){
		return succ;
	}


}

